package com.leetcode.No0875;

import java.util.Arrays;

/**
 * @program: Solution
 * @description: 875. 爱吃香蕉的珂珂
 * @author: Wang Zhihua
 * @date: 2022-06-10
 */
public class Solution {

    private int h;

    public int minEatingSpeed(int[] piles, int h) {

        Arrays.sort(piles);
        this.h = h;

        // left、right是k取值的左右区间，整数
        int left = 1;
        int right = piles[piles.length - 1];

        return binarySearch(piles, left, right);

    }

    private int binarySearch(int[] piles, int left, int right) {
        if (left == right) {
            return right;
        }

        int middle = (left + right) / 2;

        // 真实的h，真实的h须<=题目中给的h才合格
        int actualH = 0;
        for (int pile : piles) {
            if (pile <= middle) {
                ++actualH;
            } else {
                actualH += (pile / middle) + (pile % middle > 0 ? 1 : 0);
            }
            if (actualH > h) {
                break;
            }
        }
        if (actualH > h) {
            return binarySearch(piles, middle + 1, right);
        } else {
            return binarySearch(piles, left, middle);
        }
    }

    public static void main(String[] args) {
//        int[] array = {3,6,7,11};
//        int h = 8;
//        System.out.println(new Solution().minEatingSpeed(array, h));
//
//        int[] array2 = {30,11,23,4,20};
//        int h2 = 5;
//        System.out.println(new Solution().minEatingSpeed(array2, h2));
//
//        int[] array3 = {30,11,23,4,20};
//        int h3 = 6;
//        System.out.println(new Solution().minEatingSpeed(array3, h3));

        int[] array4 = {312884470};
        int h4 = 312884469;
        System.out.println(new Solution().minEatingSpeed(array4, h4));
    }

}
